package Hot100.Medium.GreedyAndDP.DynamicPlanning;

public class LC53_SumOfSubArray {
    public static void main(String[] args) {
        int[] nums = {5, 4, -1, 7, 8};

    }

    public int maxSubArray(int[] nums){
        if(nums.length == 0){
            return 0;
        }
        // 确定dp数组含义,dp[i]表示包括下标i（以nums[i]为结尾）的最大连续子序列和
        int[] dp = new int[nums.length];
        // 初始化dp数组
        // dp[0]显然等于数组中第一个元素，直接赋值
        dp[0] = nums[0];
        int res = nums[0];
        // 确定递推公式，时刻参照dp数组含义，每到一个下标i，前面的i-1个数的和可能为正或者负，因此为正数就直接加入进去，为负数就重新开始一个子序列，取大的那一个即可
        // 因此dp[i] = max(dp[i - 1] + nums[i], nums[i])
        // 最后确定遍历顺序，从前往后遍历即可
        for(int i = 1; i < nums.length; i++){
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            res = res > dp[i] ? res : dp[i];// res保存dp中最大的值。
        }
        return res;
    }
}
